import java.util.*;


public class Leetcode617 {

    public static void main(String[] args) {
        List<Integer> a = Arrays.asList(1, 3, 2, 5, null, null, null);
        TreeNode tree1 = createTree(a);

        List<Integer> b = Arrays.asList(2, 1, 3, null, 4, null, 7);
        TreeNode tree2 = createTree(b);

        TreeNode mergeTree = mergeTrees(tree1, tree2);

        System.out.println(mergeTree);

    }

    private static TreeNode createTree(List<Integer> a) {
        int i = 1;
        TreeNode root = new TreeNode(a.get(0));  // 根节点
        TreeNode current;
        Integer value;

        //层序创建二叉树
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (i < a.size()) {
            current = queue.poll();//从链表中移除并获取第一个节点
            value = a.get(i++);
            if (value != null) {
                TreeNode left = new TreeNode(value);
                current.left = left;//创建当前节点的左孩子
                queue.offer(left); // 在链表尾部 左孩子入队
            }
            value = a.get(i++);
            if (value != null) {
                TreeNode right = new TreeNode(value);
                current.right = right;//创建当前节点的右孩子
                queue.offer(right);// 在链表尾部 右孩子入队
            }
        }
        return root;
    }

    public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 != null) {
            if (root2 != null) {
                root1.val = root1.val + root2.val;

                root1.left = mergeTrees(root1.left, root2.left);
                root1.right = mergeTrees(root1.right, root2.right);
            }
            return root1;
        } else {
            if (root2 != null) {
                root1 = root2;
                return root1;
            } else {
                return null;
            }
        }
    }
}
